package com.study.lintcode.my.code_20;

import java.util.Stack;

/**********************************************************************
 * &lt;p&gt;文件名：Example_12.java &lt;/p&gt;
 * &lt;p&gt;文件描述：(@link https://www.lintcode.com/problem/min-stack/)
 * @project_name：LintCode
 * @author zengshunyao
 * @create 2019/1/5 23:58 
 * @history
 * @department：政务事业部
 * Copyright ChengDu Funi Cloud Code Technology Development CO.,LTD 2014 
 *                    All Rights Reserved.
 */
public class Example_12 {
    static class MinStack {
        Stack<Integer> stack;
        int min;

        public MinStack() {
            // do intialization if necessary
            stack = new Stack<Integer>();
            min = 0;
        }

        /*
         * @param number: An integer
         * @return: nothing
         */
        public void push(int number) {
            // write your code here
            if (stack.size() == 0) {
                stack.push(number);
                min = number;
            } else {
                if (number < min) {
                    //5,4,3,2

                    //5-> 5   5   5
                    //4->2*4-5=3 =>4  [5,3]   5,4
                    //5,4,3

                    //5->5    5   5
                    //4->2*4-5=3 =>4  [5,3]      5,4
                    //3->2*3-4=2 =>3  [5,3,2]    5,4,3

                    //5->5    5   5
                    //4->2*4-5=3 =>4  [5,3]      5,4
                    //3->2*3-4=2 =>3  [5,3,2]    5,4,3
                    //2->2*2-3=1 =>2  [5,3,2,1]  5,4,3,2
                    stack.push(2 * number - min);
                    min = number;
                } else {
                    stack.push(number);
                }
            }
        }

        /*
         * @return: An integer
         */
        public int pop() {
            // write your code here
            if (!stack.isEmpty()) {
                int temp = stack.pop();//2->2*2-3=1 =>2  [5,3,2,1]  5,4,3,2
                if (temp < min) {//1<2
                    int num = min;//2
                    min = 2 * min - temp;//2*2-1->min=3
                    temp = num;//1
                }
                return temp;
            } else {
                return min;
            }
        }

        /*
         * @return: An integer
         */
        public int min() {
            // write your code here
            return min;
        }
    }

    public static void main(String[] args) {
        Example_12.MinStack minStack = new Example_12.MinStack();
        minStack.push(1);// 1,[1]
        System.out.println(minStack.pop());//1,[]
        minStack.push(2);//1,[2]
        minStack.push(3);//1,[2,3]
        System.out.println(minStack.min());//1
        minStack.push(1);//1,[2,3,1]
        System.out.println(minStack.min());
    }
}
